#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 112. 路径总和.py
@time: 2022/1/22 13:26
@desc: https://leetcode-cn.com/problems/path-sum/submissions/
> 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。

1. Ot(N), Os(height)
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root: return False
        def dfs(root, targetSum):
            if not root: return False
            targetSum -= root.val
            if targetSum==0 and not root.left and not root.right: return True
            return dfs(root.left, targetSum) or dfs(root.right, targetSum)

        return dfs(root, targetSum)